// Copyrights by Kenneth Lee, 2022. All Rights Reserved
#include "value.hpp"
#include "ut.hpp"

static bool with_id = false;

ValComp *create_node(int v) {
	ValComp *p = new ValComp(1);
	p->vals[0] = v;
	return p;
}

ValComp *create_left(ValComp *n, int v) {
	n->left = create_node(v);
	n->left->parent = n;
	return n->left;
}

ValComp *create_right(ValComp *n, int v) {
	n->right = create_node(v);
	n->right->parent = n;
	return n->right;
}

void create_children(ValComp *n, int lv, int rv) {
	create_left(n, lv);
	create_right(n, rv);
}

/* find a val from root r */
ValComp *find_node(ValComp *r, int v) {
	ValComp *ret;

	if (r->vals[0] == v)
		return r;

	if (r->left) {
		ret = find_node(r->left, v);
		if (ret)
			return ret;
	}

	if (r->right) {
		ret = find_node(r->right, v);
		if (ret)
			return ret;
	}

	return NULL;
}

static void print_p(ValComp *p) {
	if (with_id)
		cout << p->vals[0] << "(" << (unsigned long)p % 100000 << ")";
	else
		cout << p->vals[0];

	if (p->left) {
		assert(p->right);
		cout << "{";
		print_p(p->left);
		cout << "|";
		print_p(p->right);
		cout << "}";
	}
}

static void print(ValComp *p) {
	print_p(p);
	cout << endl;
}

static void print_and_free(ValComp *p) {
	print(p);

	/* keep the memory so the memory address will not be reused */
	if (!with_id)
		free_tree(p);
}

int main(void) {
	with_id = false;

	/* create a tree
			1
		       / \
		      2   3
			 / \
			4   5
		       / \  /\
		      6   7 8 9
	*/
	ValComp *root = create_node(1);
	create_children(root, 2, 3);
	create_children(find_node(root, 3), 4, 5);
	create_children(find_node(root, 4), 6, 7);
	create_children(find_node(root, 5), 8, 9);

	/* compare the clone manually */
	cout << "0: ";
	print_and_free(root->clone());

	for (int i = 1; i < 10; i++) {
		cout << i << ": ";
		ValComp *p = find_node(root, i);
		p = p->clone_tree();
		ut_assert(p->vals[0] == i);
		print_and_free(p->find_root());
	}
	
	free_tree(root);
	return 0;
}
